package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 46. 全排列
 * 
 * https://leetcode.cn/problems/permutations/
 * 
 * @author jie.deng
 *
 */
class Question0046Solution01 {

	public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> retList = new ArrayList<>();
		Set<Integer> chosenSet = new HashSet<>();
		List<Integer> chosenList = new ArrayList<>();
		permute(0, chosenList, chosenSet, nums, retList);
		return retList;
	}

	/**
	 * 
	 * @param level      递归的深度
	 * @param chosenList 状态变量 已选择的数据
	 * @param chosenSet  辅助变量 用于剪枝
	 * @param nums       不变量
	 * @param retList    不变量
	 */
	private void permute(int level, List<Integer> chosenList, Set<Integer> chosenSet, int[] nums,
			List<List<Integer>> retList) {
		int len = nums.length;
		// 每次都是从nums[0...len-1]中选择一个，一共要选择len次，第len次时结束
		if (level == len) {
			retList.add(new ArrayList<>(chosenList));
			return;
		}
		for (int i = 0; i < len; i++) {
			// 当前层逻辑
			if (!chosenSet.add(nums[i])) {
				// 剪枝：选择的数据和之前已选的数据重复了
				continue;
			}
			chosenList.add(nums[i]);
			permute(level + 1, chosenList, chosenSet, nums, retList);

			// 状态还原，继续当前层其他选择
			chosenList.remove(chosenList.size() - 1);
			chosenSet.remove(nums[i]);
		}
	}

}